Timing Attacks
Here is the golden rule of writing code that is “constant-time”:
Secret information may only be used in an input to an instruction if that input has no impact on what resources will be used and for how long.
In practice, this golden rule has a few implications:
Secret values cannot be used to decide what code to execute next (i.e. it cannot be used as a condition to a branch instruction)
Secret values cannot be used to decide what memory address to access.
Secret values cannot be used as input to variable-time instructions like DIV on x86 (smaller numbers divide faster).
Refs
A beginner's guide to constant-time cryptography
https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html
Comprehensive timing leak protection for Rust programs
https://github.com/timmclean/rust-timing-shield
https://www.nccgroup.trust/globalassets/our-research/us/whitepapers/TimeTrial.pdf
Timing Attacks on ECDSA, ECDHE, AES and SHA2
https://crypto.stackexchange.com/questions/11300/timing-attacks-on-ecdsa-ecdhe-aes-and-sha2
Montgomery ladder
Security of rust-timing-shield
https://www.chosenplaintext.ca/open-source/rust-timing-shield/security
Tools
Subtle: Pure-Rust traits and utilities for constant-time cryptographic implementations.
https://github.com/dalek-cryptography/subtle
https://doc.dalek.rs/subtle/
rust-timing-shield based on
Popular examples
curve25519 secret keyの2^254 positionは常に1にset
montgomery ladderにおけるmulでtiming attackを防ぐ
most significant bitsの探索で生じるtiming leakage問題
常にbit fixedしておくことで対処
code:1
Q0 = P;
Q1 = 2*P;
for(int i = log2(exponent) - 2; i >= 0; --i)
{
Q bit(exponent, i) = 2*Q bit(exponent, i);
Q!bit(exponent, i) = Q0 + Q1;
}
return Q0;
https://crypto.stackexchange.com/questions/11810/when-using-curve25519-why-does-the-private-key-always-have-a-fixed-bit-at-2254/11818
Audit reports
条件分岐によりb > aかどうかのtiming leakの可能性。
https://gyazo.com/a141eb80db631313eb8a3a94cb2abff6
https://gyazo.com/de80e2cf211b527351f24603ac8094a1